package 排序;

import java.util.Arrays;

/**
 * 使用最广泛的排序算法
 * 原理上是一种分治算法，将一个数组分为两部分，对这两部分独立的排序，然后整体有序
 * 与归并排序的区别：
 * 1）：归并排序虽然也是把数组分为两部分，但是归并排序需要在部分有序后再做一次排序来让整体有序；
 * 但是快速排序是：部分有序了，整体自然就有序了，无需对整体再一次排序。
 * 2）：归并排序的数组切分是平分，但是快速排序的数组切分是根据数组内容由函数产生的
 */
public class 快速排序 {

    public static void quickSort(int[] a, int start, int end) {
        if (end <= start) {
            return;
        }
        // j 是中分点，parttion算法是关键
        int j = partition(a, start, end);
        quickSort(a, start, j - 1);// 针对左边排序
        quickSort(a, j + 1, end); // 针对右边排序
    }

    private static boolean less(Comparable v, Comparable w) {
        // 若 v 小于 w 则返回负数
        return v.compareTo(w) < 0;
    }

    private static void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /*
    这段代码按照a[start]的值v进行切分。
    当指针i和j相遇时主循环退出。
    在循环中，a[i]小于v时我们增大i，a[j]大于v时我们减小j，
    然后交换a[i]和a[j]来保证i左侧的元素都不大于v, j右侧的元素都不小于V。
    当指针相遇时交换a[start]和a[j]，切分结束(这样切分值就留在a[j]中了)。
     */
    private static int partition(int[] a, int start, int end) {
        // i、j 两根指针分别从左右开始寻找第一个大于 v 的与第一个小于 v 的值
        int i = start;
        int j = end + 1;
        int v = a[start];
        while (true) {
            // 找到第一个大于 v 的值与 i
            while (less(a[++i], v)) {
                if (i == end) {
                    break;
                }
            }
            // 找到第一个小于 v 的值与 j
            while (less(v, a[--j])) {
                if (j == start) {
                    break;
                }
            }
            // i、j 指针相交后
            if (i >= j) {
                break;
            }
            // 交换 i、j 处的值，确保 i 左边的都不大于 v，j 右边的都不小于 v
            exch(a, i, j);
        }
        exch(a, start, j);// 将 V = a[j]放入正确的位置
        return j;
    }

    public static void main(String[] args) {
//        int[] a = {12, 6, 9, 3, 78, 3, 3, 4};
        int[] a = {9, 7, 1, -8, -1, -18, 100};
        System.out.println(Arrays.toString(a));
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));

    }
}
